package com.duckygo.towerdefense.game.astar;

import java.util.Collection;
import java.util.Collections;
import java.util.Comparator;
import java.util.Vector;

import com.duckygo.towerdefense.game.sprites.Sprite;
import com.duckygo.towerdefense.game.sprites.Sprite2D;
import com.duckygo.towerdefense.game.sprites.Terrain2DSprite;

	
	public class AStar {
		
		public static final int MAP_WIDTH = 20;
		public static final int MAP_HEIGHT = 20;
		
		
		private AStarNode start;
		private AStarNode goal;
		
		private AStarNode[][] map;
		
		public Vector<AStarNode> open;
		
		public Vector<AStarNode> closed;
		
		
		public AStar(Terrain2DSprite map) {
			this.map = createMap(map);
		}
		
		
		public Vector<AStarNode> getWalkable(Sprite2D start, int cost) {
			this.start = new AStarNode((int)(start.x % MAP_WIDTH),(int)(start.y / MAP_HEIGHT));
			
			open = new Vector<AStarNode>();
			closed = new Vector<AStarNode>();
			this.start.h = 0;
			this.start.g = 0;
			
			open.add(this.start);
			closed.add(this.start);

					
			while(open.size() > 0){
				AStarNode node = open.lastElement();open.remove(open.size() - 1);
				
				for (AStarNode n : neighbors(node, false)) {
					if (!open.contains(n) && !closed.contains(n)) {
						open.add(n);
						closed.add(n);
							
					//	n.h = width - dist(this.start, n); 
						n.g = node.g + 1;
						
					} else if (node.g < n.g - 1) {
						n.g = node.g + 1;
					}
				}
					
			}
			
			
//			closed = closed.filter(function(e:AStarNode, i:int, arr:Array):Boolean {
//				return e.g <= cost;
//			});

			return closed;			
		}
		
		public Vector<AStarNode> solve(AStarNode start, AStarNode goal) {
			this.start = start;
			this.goal = goal; 
			open = new Vector<AStarNode>();
			closed = new Vector<AStarNode>();
			this.map[this.goal.x][this.goal.y].walkable = true;
			
			AStarNode node = this.start;
			node.h = dist(this.goal);
			open.add(node);
			
			boolean solved = false;
			int i = 0;
			
			
			while(!solved) {
				
				if (i++ > 10000) throw new Error("Overflow");
				
				Collections.sort(open, new Comparator<AStarNode>() {
					
					@Override
					public int compare(AStarNode object1, AStarNode object2) {
						return (int) (object1.getF() - object2.getF());
					}
				});
				
				if (open.size() <= 0) break;
				node = open.get(0); open.remove(0);
				closed.add(node);
				
				if (node.x == goal.x && node.y == goal.y) {
					solved = true;
					break;
				}
				
				for (AStarNode n : neighbors(node)) {
					if (!open.contains(n) && !closed.contains(n)) {
						open.add(n);
						n.parent = node;
						n.h = dist(n);
						n.g = node.g;
					} else {
						float f = n.g + node.g + n.h;
						if (f < n.getF()) {
							n.parent = node;
							n.g = node.g;
						}
					}
				}
			}

			if (solved) {
				Vector<AStarNode> solution = new Vector<AStarNode>();
				solution.add(node);
				while (node.parent != null && node.parent != this.start) {
					node = node.parent;
					solution.add(node);
				}
				solution.add(node);
				
				Collections.reverse(solution);
				return solution;
			} else {
				return null;
			}
		}
		
//		private function distManhattan(n1:AStarNode, n2:AStarNode=null):Number {
//			if (n2 == null) n2 = goal;
//			return Math.abs(n1.x-n2.x)+Math.abs(n1.y-n2.y);
//		}
//		
		
		private float dist(AStarNode n1) {
			return dist(n1, null);
		}
		
		private float dist(AStarNode n1, AStarNode n2) {
			if (n2 == null) n2 = goal;
			return (float) Math.sqrt(Math.pow((n1.x - n2.x),2) + Math.pow((n1.y - n2.y), 2));
		}
		
		
		private Vector<AStarNode> neighbors(AStarNode node) {
			return neighbors(node, true);
		}
		
		private Vector<AStarNode> neighbors(AStarNode node, boolean inc) {
			int x = node.x;
			int y = node.y;
			AStarNode n = null;
			Vector<AStarNode> a = new Vector<AStarNode>();
			int cost = 1;
			
			
			// 0
			if (x > 0) {
				if ((x % 2) == 1) {
					if (y > 0) {
						n = map[x - 1][y - 1];
					}
				} else {
					n = map[x - 1][y];
				}
				if (n != null && n.walkable) {
					if(inc) n.g += cost;
					a.add(n);
				}
			}
			
			n = null;
			// 1
			if (x > 0) {
				if ((x % 2) == 0) {
					if (y + 1 < MAP_HEIGHT) {
						n = map[x - 1][y + 1];
					}
				} else {
					n = map[x - 1][y];
				}
				if (n != null && n.walkable) {
					if(inc) n.g += cost;
					a.add(n);
				}
			} 
			
			n = null;
			// 2
			if (y + 1 < MAP_HEIGHT) {
				n = map[x][y + 1];
				if (n.walkable) {
					if(inc) n.g += cost;
					a.add(n);
				}
			}
			
			n = null;
			// 3
			if (x + 1 < MAP_WIDTH) {
				if ((x % 2) == 0) {
					if (y + 1 < MAP_HEIGHT) {
						n = map[x + 1][y + 1];
					}
				} else {
					n = map[x + 1][y];
				}
				if (n != null && n.walkable) {
					if(inc) n.g += cost;
					a.add(n);
				}
			}
			
			n = null;
			// 4
			if (x + 1 < MAP_WIDTH) {
				if ((x % 2) == 1) {
					if (y > 0) {
						n = map[x + 1][y - 1];
					}
				} else {
					n = map[x + 1][y];
				}
				if (n != null && n.walkable) {
					if(inc) n.g += cost;
					a.add(n);
				}
			} 
			
			n = null;
			// 5
			if (y > 0) {
				n = map[x][y - 1];
				if (n.walkable) {
					if(inc) n.g += cost;
					a.add(n);
				}
			}
			
			return a;
		}
		
		private AStarNode[][] createMap(Terrain2DSprite game) {
			AStarNode[][] a = new AStarNode[MAP_WIDTH][MAP_HEIGHT];
			for (int x = 0; x < MAP_WIDTH; x++) {
				for (int y = 0; y < MAP_HEIGHT; y++) {
					a[x][y] = new AStarNode(x, y, true);
					a[x][y].walkable = game.isWalkable(x, y);
				}
			}
			
//			for(Sprite sprite : game.children) {
//				if (sprite instanceof Sprite2D) {
//					continue;
//				}
//				
//				Sprite2D obj = (Sprite2D) sprite;
//				
//				int x = (int) ((obj.x + obj.width / 2) / (((Sprite2D)game).width / MAP_WIDTH));
//				int y = (int) ((obj.y + obj.height / 2) / (((Sprite2D)game).height / MAP_HEIGHT));
//				
//				a[x][y].walkable = true;
//			}
			
			return a;
		}
}




